#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
//typedef char STDataType;
//typedef struct Stack
//{
//    STDataType* a;
//    int top;//栈顶
//    int capacity;//容量
//}ST;
//
////判空
//bool STEmpty(ST* ps)
//{
//    assert(ps);
//    return ps->top == 0;
//}
////初始化
//void STInit(ST* ps)
//{
//    assert(ps);
//    ps->a = NULL;
//    ps->capacity = 0;
//    ps->top = 0;
//}
////销毁
//void STDestroy(ST* ps)
//{
//    free(ps->a);
//    ps->a = NULL;
//    ps->capacity = 0;
//    ps->top = 0;
//}
////入栈
//void STPush(ST* ps, STDataType x)
//{
//    assert(ps);
//    if (ps->capacity == ps->top)
//    {
//        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//        STDataType* p = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
//        ps->a = p;
//        ps->capacity = newcapacity;
//    }
//    ps->a[ps->top] = x;
//    ps->top++;
//}
////出栈
//void STPop(ST* ps)
//{
//    assert(ps);
//    assert(ps->a);
//    assert(!STEmpty(ps));
//    ps->top--;
//}
////取栈顶元素
//STDataType STTop(ST* ps)
//{
//    assert(ps);
//    assert(ps->a);
//    assert(!STEmpty(ps));
//    return ps->a[ps->top - 1];
//}
//
//bool isValid(char* s)
//{
//    ST ps;
//    STInit(&ps);
//    int i = 0;
//    for (i = 0; i < strlen(s); i++)
//    {
//        if (s[i] == '(' || s[i] == '{' || s[i] == '[')//左括号入栈
//        {
//            STPush(&ps, s[i]);
//        }
//        else//右括号与栈顶元素进行匹配
//        {
//            if (STEmpty(&ps))//栈中为空，说明括号数量不匹配
//            {
//                return false;
//            }
//            else if ((STTop(&ps) == '(' && s[i] != ')') ||
//                (STTop(&ps) == '[' && s[i] != ']') ||
//                (STTop(&ps) == '{' && s[i] != '}'))//栈中不为空，但括号样式不匹配
//            {
//                return false;
//            }
//            else//匹配成功，栈顶元素出栈
//            {
//                STPop(&ps);
//            }
//        }
//    }
//    if (STEmpty(&ps))//全部遍历完之后，栈中为空，说明全部匹配成功
//    {
//        return true;
//    }
//    else//栈中不为空，说明数量不匹配
//    {
//        return false;
//    }
//    STDestroy(&ps);
//}
//int main()
//{
//    char arr[100] = { 0 };
//    gets(arr);
//    printf("%d\n", isValid(arr));
//    return 0;
//}
 
//
////用栈实现队列
//typedef int STDataType;
//typedef struct Stack
//{
//    STDataType* a;
//    int top;//栈顶
//    int capacity;//容量
//}ST;
//typedef struct
//{
//    ST push;
//    ST pop;
//} MyQueue;
//
////初始化
//void STInit(ST* ps)
//{
//    assert(ps);
//    ps->a = NULL;
//    ps->capacity = 0;
//    ps->top = 0;
//}
////判空
//bool STEmpty(ST* ps)
//{
//    assert(ps);
//    return ps->top == 0;
//}
////销毁
//void STDestroy(ST* ps)
//{
//    free(ps->a);
//    ps->a = NULL;
//    ps->capacity = 0;
//    ps->top = 0;
//}
////入栈
//void STPush(ST* ps, STDataType x)
//{
//    assert(ps);
//    if (ps->capacity == ps->top)
//    {
//        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//        STDataType* p = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
//        ps->a = p;
//        ps->capacity = newcapacity;
//    }
//    ps->a[ps->top] = x;
//    ps->top++;
//}
//
////出栈
//void STPop(ST* ps)
//{
//    assert(ps);
//    assert(ps->a);
//    assert(!STEmpty(ps));
//    ps->top--;
//}
////取栈顶元素
//STDataType STTop(ST* ps)
//{
//    assert(ps);
//    assert(ps->a);
//    assert(!STEmpty(ps));
//    return ps->a[ps->top - 1];
//}
////创建我的队列
//MyQueue* myQueueCreate()
//{
//    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
//    STInit(&obj->push);
//    STInit(&obj->pop);
//    return obj;
//}
////入队
//void myQueuePush(MyQueue* obj, int x)
//{
//    STPush(&obj->push, x);
//}
////出队
//int myQueuePop(MyQueue* obj)
//{
//    if (STEmpty(&obj->pop))
//    {
//        while (!STEmpty(&obj->push))
//        {
//            STDataType x = STTop(&obj->push);
//            STPop(&obj->push);
//            STPush(&obj->pop, x);
//        }
//    }
//    STDataType front = STTop(&obj->pop);
//    STPop(&obj->pop);
//    return front;
//}
////取队头
//int myQueuePeek(MyQueue* obj)
//{
//    if (STEmpty(&obj->pop))
//    {
//        while (!STEmpty(&obj->push))
//        {
//            STDataType x = STTop(&obj->push);
//            STPop(&obj->push);
//            STPush(&obj->pop, x);
//        }
//    }
//    STDataType front = STTop(&obj->pop);
//    return front;
//}
////我的队列判空
//bool myQueueEmpty(MyQueue* obj)
//{
//    return (STEmpty(&obj->push) && STEmpty(&obj->pop));
//}
////销毁我的队列
//void myQueueFree(MyQueue* obj)
//{
//    STDestroy(&obj->push);
//    STDestroy(&obj->pop);
//    free(obj);
//}
//int main()
//{
//    MyQueue* obj = myQueueCreate();
//    int i = 0;
//    for (i = 1; i <= 5; i++)
//    {
//        myQueuePush(obj, i);
//    }
//    for (i = 0; i < 4; i++)
//    {
//        int k = myQueuePop(obj);
//        printf("%d ", k);
//    }
//    myQueuePush(obj, 10);
//    myQueuePush(obj, 20);
//    for (i = 0; i < 3; i++)
//    {
//        int k = myQueuePop(obj);
//        printf("%d ", k);
//    }
//    myQueueFree(obj);
//    return 0;
//}

//用队列实现栈
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;
typedef struct
{
	Que p1;
	Que p2;
} MyStack;
//判空 ：空返回1，非空返回0
bool QueueEmpty(Que* pq)
{
	assert(pq);
	return pq->head == NULL;
}
//初始化
void QueueInit(Que* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
//销毁
void QueueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* p = cur->next;
		free(cur);
		cur = p;
	}
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
//入队
void QueuePush(Que* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = newnode;
		pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
//出队
void QueuePop(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//要有数据
	if (pq->head->next == NULL)//只有一个节点
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;
	}
	else
	{
		QNode* cur = pq->head->next;
		free(pq->head);
		pq->head = cur;
	}
	pq->size--;
}
//取队头
QDataType QueueFront(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
//取队尾
QDataType QueueBack(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
//有效数据
int QueueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}
//创建我的栈
MyStack* myStackCreate()
{
	MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&obj->p1);
	QueueInit(&obj->p2);
	return obj;
}
//入栈
void myStackPush(MyStack* obj, int x)
{
	if (!QueueEmpty(&obj->p1))
	{
		QueuePush(&obj->p1, x);
	}
	else
	{
		QueuePush(&obj->p2, x);
	}
}
//出栈
int myStackPop(MyStack* obj)
{
	QDataType top = 0;
	if (!QueueEmpty(&obj->p1))
	{
		while (QueueSize(&obj->p1) > 1)
		{
			QDataType a = QueueFront(&obj->p1);
			QueuePop(&obj->p1);
			QueuePush(&obj->p2, a);
		}
		top = QueueFront(&obj->p1);
		QueuePop(&obj->p1);
	}
	else
	{
		while (QueueSize(&obj->p2) > 1)
		{
			QDataType a = QueueFront(&obj->p2);
			QueuePop(&obj->p2);
			QueuePush(&obj->p1, a);
		}
		top = QueueFront(&obj->p2);
		QueuePop(&obj->p2);
	}
	return top;
}
//取栈顶
int myStackTop(MyStack* obj)
{
	if (!QueueEmpty(&obj->p1))
	{
		return QueueBack(&obj->p1);
	}
	else
	{
		return QueueBack(&obj->p2);
	}
}
//判空
bool myStackEmpty(MyStack* obj)
{
	return (QueueEmpty(&obj->p1) && QueueEmpty(&obj->p2));
}
//销毁我的栈
void myStackFree(MyStack* obj)
{
	QueueDestroy(&obj->p1);
	QueueDestroy(&obj->p2);
	free(obj);
}

int main()
{
	MyStack* obj = myStackCreate();
	int i = 0;
	for (i = 1; i <= 5; i++)
	{
		myStackPush(obj, i);
	}
	for (i = 0; i < 3; i++)
	{
		int k = myStackPop(obj);
		printf("%d ", k);
	}
	myStackPush(obj, 10);
	myStackPush(obj, 20);
	for (i = 0; i < 4; i++)
	{
		int k = myStackPop(obj);
		printf("%d ", k);
	}
	myStackFree(obj);
    return 0;
}